BZOJ3143【HNOI2013】游走 <高斯消元>

Problem

【HNOI2013】游走

Description

一个无向连通图，顶点从编号到，边从编号到。
在该图上进行随机游走，初始时在号顶点，每一步以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当到达号顶点时游走结束，总分为所有获得的分数之和。
现在请你对这条边进行编号，使得获得的总分的期望值最小。

Input

第一行是正整数和，分别表示该图的顶点数和边数。
接下来行每行是整数，表示顶点与顶点之间存在一条边。

Output

仅包含一个实数，表示最小的期望值，保留位小数。

Sample Input

Sample Output

3.333

Explanation

边编号为，边编号，边编号为。

HINT

保证图为无向简单连通图

标签：高斯消元

Solution

大致思路是求出每条边的期望经过次数，然后贪心选择边权。
然而对于边来说，并不好确定其期望经过次数，而点的期望经过次数则更好求。

设为到达点并继续向下一个点移动的期望次数。那么对于普通的点（非起点或终点），其只能从与其相邻的点走过来，于是对于点，从连出去的点的集合为，那么，其中为点的度数。而对于号点，初始时一定在号点上，因此一定初始就有次的经过次数，而游走过程中的情况与普通点相同，于是。对于号点，由于到了后不能继续走动，即只进不出，于是一定不会经过（因为前面经过的定义是要有向下一个点移动的可能），因此。
于是有方程组

用高斯消元可以解得。

对于一条边，其端点为和，要经过必定只能是从到或从到。在时有的概率走这条边，在时有的概率走这条边，于是第条边的期望经过次数为。
求出后从大到小排序，贪心使得期望经过次数越大的边权越小，即可得到最小的期望路径长度。

Code

#include <bits/stdc++.h>
#define EPS 1e-7
#define MAX_N 500
#define MAX_M 250000
using namespace std;
typedef double dnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, u[MAX_M+5], v[MAX_M+5], d[MAX_N+5];
dnt f[MAX_N+5][MAX_N+5], x[MAX_N+5], y[MAX_M+5];
void Gauss() {
    for (int i = 1, t; i <= n; i++) {
        for (t = i; t <= n; t++) if (fabs(f[i][t]) >= EPS) break;
        if (t > n) continue; swap(f[i], f[t]);
        for (int j = 1; j <= n; j++) if (i^j) {
            dnt div = f[j][i]/f[i][i];
            for (int k = 1; k <= n+1; k++)
                f[j][k] -= f[i][k]*div;
        }
    }
    for (int i = 1; i <= n; i++) x[i] = f[i][n+1]/f[i][i];
}
int main() {
    read(n), read(m); dnt ans = 0;
    for (int i = 1; i <= m; i++)
        read(u[i]), read(v[i]), d[u[i]]++, d[v[i]]++;
    for (int i = 1; i <= m; i++)
        f[u[i]][v[i]] -= 1.0/d[v[i]], 
        f[v[i]][u[i]] -= 1.0/d[u[i]];
    for (int i = 1; i <= n; i++) f[n][i] = 0;
    for (int i = 1; i <= n; i++) f[i][i] = 1;
    f[1][n+1] = 1, Gauss();
    for (int i = 1; i <= m; i++) y[i] = x[u[i]]/d[u[i]]+x[v[i]]/d[v[i]];
    sort(y+1, y+m+1); for (int i = 1; i <= m; i++) ans += y[i]*(m-i+1);
    return printf("%.3lf\n", ans), 0;
}